#ifndef CALCULATOR_H
#define CALCULATOR_H

#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <cmath>
#include <ctype.h>
#include <cstdlib>

/**
 * 算数操作符的优先级
 */
enum PRIO_LV
{
    PRIO_LV0 = 0,
    PRIO_LV1 = 1,
    PRIO_LV2 = 2,
    PRIO_LV3 = 3,
    PRIO_LV4 = 4,
    PRIO_LV5 = 5    
};

/**
 * 输入表达式的错误类型
 */
enum WRONG_TYPE
{
    INVAL_CHAR, /// 不合法的字符
    PAREN_ERROR, /// 括号不匹配
    WRONG_EXP, /// 错误的运算逻辑
    DIVISOR_ZERO, /// 除数为0
    FLOAT_ERROR, /// 小数格式错误
    EMPTY_EXP /// 空表达式，比如"","()"等
};

/**
 * 计算后缀表达式的方式
 * 
 */
enum METHOD
{
    STACK = 1, /// 数字栈
    TREE = 2 /// 二叉树
};


class calculator
{
private:
    std::string infix; /// 存储中缀表达式
    std::vector<std::string> postfix; /// 存储后缀表达式
    // 获取算术操作符的优先级
    int getPrior(char c);
    // 标准化表达式的格式
    void stdExp(std::string & s, std::string::iterator & it);
    // 将中缀表达式转化为后缀表达式
    void inToPostfix();
    // 由后缀表达式计算结果
    double evalPostFix(METHOD method);
    // 采用栈计算后缀表达式
    double evalPostFix_Stack();
    // 采用二叉树计算后缀表达式
    double evalPostFix_BinTree();
    // 内部计算接口
    double _calc(METHOD method);
    

public:
    calculator() {}
    // 构造函数
    calculator(const std::string & token)
    {
	init(token);
    }
    // 初始化，并输出计算器的相关信息
    inline void init(const std::string & token)
    {
	infix = token;	
    }    
    // 得到计算器的介绍信息
    inline void get_info()
    {
	std::cout << "-------------------五则混合计算器-------------------" << std::endl;
	std::cout << "支持运算符:  + - * / ^ ()" << std::endl;
	std::cout << "运算符的优先级:  " << "+ = - < * = / < ^ < (" << std::endl;
	std::cout << "-----------------------------------------------------" << std::endl;
    }
    // 计算结果
    double calc(METHOD method = STACK)
    {
	return _calc(method);
    }
    // 得到标准化的中缀表达式
    std::string get_infix()
    {
	return infix;
    }
    // 得到后缀表达式
    std::string get_postfix();
};

/** 
 * 获取算术操作符c的优先级
 * 优先级排序满足：+ < - < * < / < ^ < (
 * @param c 
 * 
 * @return 
 */
int calculator::getPrior(char c)
{
    switch(c){
    case '+':
	return PRIO_LV1;
	break;
    case '-':
	return PRIO_LV2;
	break;
    case '*':
	return PRIO_LV3;
	break;
    case '/':
	return PRIO_LV4;
	break;
    case '^':
	return PRIO_LV5;
	break;
    case '(':
	return PRIO_LV0;
	break;
    default:
	std::cout << "Not an operator!" << std::endl;
	exit(-1);
    }
}

/** 
 * 中缀表达式标准格式化
 * 转为后缀表达式时，每一步之前都要进行
 * @param it 
 */
void calculator::stdExp(std::string & s, std::string::iterator & it)
{
    // 当前项为'.'，或者【为'+'或'-'，并且是表达式首项或者左括号后第一项】
    if ( *it == '.' || ((it == s.begin() || *(it-1) == '(') &&
			(*it == '+' || *it == '-') )
	)
	// 前方补零
	it = s.insert(it,'0');
    // 当前项是表达式首项或者左括号后第一项，且为除'('之外的其他操作符
    else if( (it == s.begin() || *(it-1) == '(') &&
	(*it == '*' || *it == '/' || *it == '^')	    
	)
	// 表达式错误
	throw WRONG_EXP;	
}

/** 
 * 得到后缀表达式
 * 
 */
void calculator::inToPostfix()
{
    // 判断中缀表达式是否为空
    if(infix.empty())
	throw EMPTY_EXP;
    // 构造符号栈
    std::stack<char> symStack;
    // 中间变量
    std::string tmp;
    std::vector<std::string> _postfix;
    // 遍历中缀表达式
    for(std::string::iterator it = infix.begin(); it != infix.end(); ++it)
    {	
	// 标准化
	stdExp(infix,it);
	// 初始化中间变量
	tmp.clear();
	// 判断当前字符的类型
	switch(*it)
	{
	case '+':
	case '-':
	case '*':
	case '/':
	case '^':
	    if(symStack.empty() || symStack.top() == '(') // 栈为空或者顶部为'('，直接入栈
		symStack.push(*it);
	    else
	    {
		while(!symStack.empty() && (getPrior(symStack.top()) >= getPrior(*it))) // 栈不为空且栈顶符号的优先级大于等于（等于不能省略）当前符号的优先级
		{
		    tmp = symStack.top();
		    _postfix.push_back(tmp);
		    symStack.pop();
		}
		// 入栈
		symStack.push(*it);
	    }
	    break;

	case '(':
	    symStack.push(*it);
	    break;
	case ')':
	    // 括号不匹配
	    if(symStack.empty())
		throw PAREN_ERROR;
	    // 栈不为空且栈顶不为'('
	    while(!symStack.empty() && symStack.top() != '(')
	    {
		tmp = symStack.top();
		_postfix.push_back(tmp);
		symStack.pop();
	    }
	    // 没有相应的'('，括号不匹配
	    if(symStack.empty())
		throw PAREN_ERROR;
	    else // 栈顶为'('
		symStack.pop();
	    break;

	default:
	    // 数字
	    if(isdigit(*it))
	    {
		tmp += *it;
		int count = 0;	//统计一个数据中小数点的个数
		// 防止数组越界以及小数处理
		while( (it+1) != infix.end() && (*(it+1) == '.' || isdigit(*(it+1))) )
		{
		    if(*(it+1) == '.')
			if(++count > 1)
			    // 大于1则说明小数格式错误
			    throw FLOAT_ERROR;
		    // 否则即为合法连续的数字，进行追加
		    tmp += *(it+1);
		    ++it;		    
		}
		// 将x.转化为x.0
		if(*it == '.')
		    tmp += '0';

		_postfix.push_back(tmp);
	    }
	    // 空格，自动跳过
	    else if(*it == ' ')
	    {
		while(*it == ' ')
		    ++it;
		--it; // 指向最后一个空格
	    }
	    else // 无效字符
		throw INVAL_CHAR;
	    break;
	} //end switch
    }// end for

    // 将栈中剩余的符号加入后缀表达式
    while(!symStack.empty())
    {	
	tmp = symStack.top();
	_postfix.push_back(tmp);
	symStack.pop();
    }
    // 赋值给全局变量postfix
    postfix = _postfix;
}

/** 
 * 由后缀表达式计算结果 
 * 可指定采用数字栈或者二叉树两种方式实现，缺省值为数字栈
 * @return result
 */
double calculator::evalPostFix(METHOD method)
{
    switch(method)
    {
    case STACK:
	return evalPostFix_Stack();
	break;
    case TREE:
	return evalPostFix_BinTree();
	break;
    default:
	std::cerr << "Wrong Computing Method Type!" << std::endl;
	exit(-1);
    }
}

/** 
 * 采用栈计算后缀表达式
 * 
 * @return result
 */
double calculator::evalPostFix_Stack()
{
    // 判断后缀表达式是否为空
    if(postfix.empty())
	throw EMPTY_EXP;
    // 构造数字栈
    std::stack<double> figStack;
    // 中间变量
    std::string tmp;
    double a,b,number;
    // 存储计算结果
    double result;
    // 遍历后缀表达式
    for(std::vector<std::string>::iterator it = postfix.begin(); it != postfix.end(); ++it)
    {
	tmp = *it;
	// 后缀表达式中的数值元素可能是多位或者小数，比如"234"、"2.34"等
	if(isdigit(tmp[0]))
	{
	    number = atof(tmp.c_str());
	    figStack.push(number);
	}
	else // 运算符号
	{
	    switch(tmp[0])
	    {
	    case '+':
		a = figStack.top(); figStack.pop();
		// 缺少被加数则报错
		if(figStack.empty())
		    throw WRONG_EXP;
		b = figStack.top(); figStack.pop(); figStack.push(b+a);
		break;
	    case '-':
		a = figStack.top(); figStack.pop();
		// 缺少被减数则报错
		if(figStack.empty())
		    throw WRONG_EXP;
		b = figStack.top(); figStack.pop(); figStack.push(b-a);
		break;
	    case '*':
		a = figStack.top(); figStack.pop();
		// 缺少被乘数则报错
		if(figStack.empty())
		    throw WRONG_EXP;
		b = figStack.top(); figStack.pop(); figStack.push(b*a);
		break;
	    case '/':
		a = figStack.top(); figStack.pop();
		// 缺少被除数则报错
		if(figStack.empty())
		    throw WRONG_EXP;
		// 除数为0
		if(a == 0)
		    throw DIVISOR_ZERO;
		b = figStack.top(); figStack.pop();		
		figStack.push(b/a);
		break;
	    case '^':
		a = figStack.top(); figStack.pop();
		// 缺少底数则报错
		if(figStack.empty())
		    throw WRONG_EXP;
		b = figStack.top(); figStack.pop(); figStack.push(pow(b,a));
		break;
	    } // end switch
	} // end else	
    } // end for
    // 栈中的元素大于1，说明表达式逻辑错误，比如 2 3 3 +
    if(figStack.size() > 1)
	throw WRONG_EXP;
    result = figStack.top();
    return result;
}

/** 
 * 采用二叉树构建表达式树，计算后缀表达式
 * 
 * @return result
 */
double calculator::evalPostFix_BinTree()
{
    return 0;
}


/** 
 * 计算表达式结果的内部函数
 * 对各种可能的错误情况处理
 * @return result
 */
double calculator::_calc(METHOD method)
{
    double result;
    try
    {
	// 得到后缀表达式
	inToPostfix();
	// 由后缀表达式计算结果
	result = evalPostFix(method);
    }    
    catch(WRONG_TYPE error)
    {
	switch(error)
	{
	case INVAL_CHAR:
	    std::cout << infix << ":\tInvalid Character Input!" << std::endl;	    
	    break;
	case PAREN_ERROR:
	    std::cout << infix << ":\tParentheses Not Matched OR Empty!" << std::endl;
	    break;
	case WRONG_EXP:
	    std::cout << infix << ":\tIllegal Operational Expression!" << std::endl;
	    break;
	case DIVISOR_ZERO:
	    std::cout << infix << ":\tDivision By Zero!" << std::endl;
	    break;
	case FLOAT_ERROR:
	    std::cout << infix << ":\tWrong Float Number Format!" << std::endl;
	    break;
	case EMPTY_EXP:
	    std::cout << infix << ":\tEmpty Expression!" << std::endl;
	    break;
	}
	throw error;
    }
    return result;
}

/** 
 * 得到后缀表达式
 * 
 * @return postfix expression
 */
std::string calculator::get_postfix()
{
    std::string _postfix;
    for(const std::string & x: postfix)
    {
	_postfix += " ";
	_postfix += x;
    }
    _postfix.erase(_postfix.begin()); // 去掉首项的空格
    return _postfix;
}


#else
#endif
